Generally, a data set includes a plurality of data records or data items, and each data record or item includes one or more fields of information and is uniquely identified by a key parameter. Depending on the nature and distribution of a particular data set, different items or keys may appear with different frequencies through the data set. The problem of detecting the most frequent items in large data sets and providing accurate frequency estimates for those items arises in many areas. For example, (i) Internet providers need to know the most frequent destinations in order to manage traffic and service quality; (ii) Social network companies need to find the most frequent interactions among the users in order to extract information about connections and relations between individuals; (iii) Retail companies need to know the most common products purchased by each customer in order to better classify the customer and design appropriate marketing campaigns; and (iv) Database engines can optimize query plans depending on the degree of skew in the underlying data and can give separate treatment to the most frequent items. Additionally an increasing number of businesses find it useful to monitor the most frequent topics in news streams or social media so as to adjust their business decisions based on these topics. In order to be practical, any algorithm that tackles this problem has to perform its computations using limited memory, usually orders of magnitude less than the size of the data set. Another key practical requirement is performing all computations in one pass—without these features, an algorithm for detecting most frequent items and estimating the associated item frequencies would not be useful for very large data sets or data streams.